/**
 * 剑指 Offer 07. 重建二叉树（与 105 同）
 * https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
 */
public class Solutions_Offer_07 {
    public static void main(String[] args) {
//        int[] preorder = {3, 9, 20, 15, 7};
//        int[] inorder = {9, 3, 15, 20, 7};  // output: {3, 9, 20, 15, 7}

        int[] preorder = {};
        int[] inorder = {};  // output: {}

        TreeNode result = buildTree(preorder, inorder);
        System.out.println(result);
    }

    // 记录索引
    private static int in = 0;
    private static int pre = 0;

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        int stop = Integer.MAX_VALUE;

        TreeNode result = buildTree(preorder, inorder, stop);
        return result;
    }

    public static TreeNode buildTree(int[] preorder, int[] inorder, int stop) {
        if (pre == preorder.length) {
            return null;
        }
        if (inorder[in] == stop) {
            in ++;
            return null;
        }
        int rootVal = preorder[pre++];
        // 创建节点对象，递归完成该节点的左右子树构造
        TreeNode root = new TreeNode(rootVal);
        // root 左子树，在中序遍历数组 inorder 中，终止的结点就是 rootVal
        root.left = buildTree(preorder, inorder, rootVal);
        // root 右子树，在中序遍历数组 inorder 中，终止的结点是父节点的父节点，即 stop
        root.right = buildTree(preorder, inorder, stop);
        return root;
    }
}
